package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-27
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个非空且只包含非负数的整数数组nums，数组的度的定义是指数组里任一元素出现频数的最大值。
 *
 * 你的任务是在 nums 中找到与nums拥有相同大小的度的最短连续子数组，返回其长度
 */
public class leetcode697 {
    public int findShortestSubArray(int[] nums) {
        HashMap<Integer, int[]> map = new HashMap<>();
        //map的value数组d，d[0]表示该数字出现次数,d[1]表示该数字出现的第一个位置，d[2]表示该数字出现的最后一个位置
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                map.get(nums[i])[0]++;
                map.get(nums[i])[2] = i;
            }else map.put(nums[i],new int[]{1,i,i});
        }

        int max = 0;
        int minLen = 0;
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int start = entry.getValue()[1], end = entry.getValue()[2];
            if (entry.getValue()[0]>max) {
                max = entry.getValue()[0];
                minLen = end-start+1;
            }else if (entry.getValue()[0]==max){
                minLen = Math.min(minLen,end-start+1);
            }
        }
        return minLen;
    }
}
